package com.c2b.algorithm.leetcode.jzoffer;

/**
 * <a href="">旋转数组的最小数字</a>
 * <p>
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。<br>
 * <p>
 * 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。<br>
 * 请返回旋转数组的最小元素。<br>例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
 * <p>
 * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：numbers = [3,4,5,1,2]
 * 输出：1
 * <p>
 * 示例 2：
 * <p>
 * 输入：numbers = [2,2,2,0,1]
 * 输出：0
 * <p>
 * 提示：
 * <p>
 * n == numbers.length<br>
 * 1 <= n <= 5000<br>
 * -5000 <= numbers[i] <= 5000<br>
 * numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转</p>
 *
 * @author c2b
 * @since 2023/3/24 16:23
 */
public class JzOffer0011MinArray_S {

    public int minArray(int[] numbers) {
        int leftIndex = 0;
        int rightIndex = numbers.length - 1;
        int mid;
        while (leftIndex < rightIndex) {
            mid = leftIndex + ((rightIndex - leftIndex) >> 1);
            if (numbers[mid] > numbers[rightIndex]) {
                // 说明处于反转节点之前的递增趋势区间上
                leftIndex = mid + 1;
            } else if (numbers[mid] < numbers[rightIndex]) {
                // 说明处于反转节点之后的递增趋势区间上，最小值在mid节点或者mid左侧
                rightIndex = mid;
            } else {
                // 不知道在何位置
                rightIndex--;
            }
        }
        return numbers[rightIndex];
    }

    public static void main(String[] args) {
        JzOffer0011MinArray_S jzOffer0011MinArray_s = new JzOffer0011MinArray_S();
        System.out.println(jzOffer0011MinArray_s.minArray(new int[]{1,3,4}));
    }
}
